More precisely, the invention relates to a signal processing method making use of a MAP (Maximum A Posteriori) type algorithm. The MAP algorithm is presented particularly clearly in the article entitled “Statistical Inference for Probabilistic Functions of Finite State Markov Chains” by L. E. Baum and T. Pertie, Ann. Math. Stat. 37: 1554-1563, 1966.
The MAP algorithm, also called the Forward-Backward (FB) algorithm, is drawing a great deal of interest at the moment. In particular, this algorithm is capable of decoding a convolutive code by associating reliability information with decoded bits, and it can beneficially be used in many applications such as applications using a “turbo-code”.
The following briefly describes the principle of the MAP algorithm. For the purposes of this description and throughout the remainder of the document, the term “MAP algorithm” includes MAP type algorithms, and also algorithms derived from MAP type algorithms, and particularly Log-MAP and Max-Log-MAP type algorithms.
Diagrammatically, the MAP algorithm may be considered as merging of information (node metrics) generated by two modified Viterbi decoders working on data in the backwards direction. Remember that the Viterbi algorithm, frequently used for decoding of received signals, consists of searching in a lattice representing the coding for the path corresponding to the most probable sequence of states, in other words searching for the path which is the minimum distance from the required sequence. This algorithm is described in the article by G. D. Forney, “The Viterbi Algorithm”, Proceedings of the IEEE, vol. 61, No. 3, Mar. 1973.
The MAP algorithm can be used to determine the likelihood ratio of the a posteriori probability of states at instant k, 0≦k≦K of a hidden Markov string with finite states, starting from observations Y0K={Y0, . . . , YK}. A Markov chain is usually defined as a collection of consecutive random states chained one behind the other, in which the changeover from one state to another is associated with a probability called the transition probability.
A Markov chain {Xk} with values in a finite space E={1, . . . N} can thus be considered, defined by a states transition matrix Π=(πi,j), with dimension N×N and an initial law ν=(νi)Ni=1 defined by νi=Prob[X0=i], ∀i∈E. According to the terminology conventionally used, a transition between two states Xk−1 and Xk is defined by a pair of states and is denoted ξk=(Xk−1, Xk). The matrix Π is a transition matrix between states associated with {Xk}, for which the elements πij are defined by:πij=Prob[Xk=j/Xk−1=i], for all i,j∈E  (1)
This document considers the case of hidden Markov models for which noisy observations are available {Yk} with value in d, collected through a channel without memory. In other words, observations {Yk} are mutually independent depending on transitions between states ξk, and each observation Yk is only dependent on the transition ξk at the same instant k. Consequently, the observed signal model can be written in the following form:Yk=H(ξk)+Bk  (2)where H(.) represents the transfer function of the channel without memory defined in E and with value in d, ξk=(Xk−1, Xk) is a pair of states at instant k with value in E×E, Yk represents an observation at instant k with value in d and where Bk is added white noise.
In the context of digital communications, the model defined by equation (2) may be applied in equalisation: the channel H(.) then represents the transmission channel in base band and Xk represents a series of symbols in the modulation alphabet, the width of which is equal to the channel memory.
During decoding of a convolutive code, H(.) then represents the code generator polynomials, and Xk represents the memory contents of the channel coder.
We will now describe the concept of the likelihood ratio calculated in the context of the MAP algorithm in more detail.
The likelihood ratio ΛkX of a set X belonging to the set of parts of E is defined as being the ratio of the a posteriori probability of set X to the a posteriori probability of the complement of X in E.
The likelihood ratio can be expressed in the form of the following equation:
                              Λ          k          X                =                                            ∑                              i                ∈                X                                      ⁢                          PAP              k              i                                                          ∑                              i                ∉                X                                      ⁢                          PAP              k              i                                                          (        3        )            
where PAPki=P[Xk=i/Y0=y0 . . . , . . . , Yk=yK], 0≦k≦K.
Classically, the MAP algorithm is associated with a lattice representation of the different states to be considered. Thus, if a convolutive coder is considered, the MAP algorithm uses the lattice representation of the variation of the coder with time, for decoding. The lattice is usually represented by a graph, in which the abscissas axis represents the time and the ordinates axis represents the different possible states. Therefore each node in the lattice is associated firstly with a state, and secondly with an instant k. The possible transitions between nodes of two successive instants k and k+1 are represented by branches.
The MAP algorithm involves two intermediate variables, called the “forward variable” and the “backward variable” respectively. These variables propagated by the MAP algorithm are calculated recursively, in the forward direction and in the backward direction respectively with respect to the lattice, and the result is a calculation of the likelihood ratio at each instant k.
These forward and backward variables defined in the remainder of the document use the probability of observing yk conditionally in the Xk=j and Xk−1=i states, expressed by the following equation:bi,j(Yk)=Prob[Yk=yk/Xk−1=i, Xk=j]  (5)
Classically, this probability is called metric. It may possibly depend on k, and is a function of the probability density of the noise Bk.
The MAP algorithm proceeds in three steps, firstly a forward recursion step, secondly a backward recursion step, and finally a data merging step.
Forward recursion consists of calculating the probabilities αik of passing through nodes representing the states Xi=i at instants k, starting from information obtained by passing through the lattice in the direct direction. The forward variable αik is thus defined as the probability of the event (Xi=i, Y0=y0, . . . Yk=yk):αik=Prob[Xi=i, Y0=y0, . . . Yk=yk]  (6)
It can be demonstrated that values of αik, 0≦k≦K are calculated recursively as follows:
      α    i          k      +      1        =            ∑              j        ∈        E              ⁢                  π                  j          ,          i                    ⁢                        b                      j            ,            i                          ⁡                  (                      Y                          k              +              1                                )                    ⁢              α        j        k            
with the initial value αio=νi, ∀i∈E.
Similarly, the backward recursion consists of calculating the probabilities βik of passing through nodes representing the states Xi=i at instants k, starting from information obtained by going through the lattice in the indirect direction. The backward variable βik is thus defined as the probability of the event (Xi=i, Yk+1=yk+1, . . . Yk=yk):βik=Prob[Xi=i, Yk+1=yk+1, . . . Yk=yk]  (7)
It can be demonstrated that βik, 0≦k≦K are calculated recursively as follows:
      β    i    k    =            ∑              j        ∈        E              ⁢                  π                  i          ,          j                    ⁢                        b                      i            ,            j                          ⁡                  (                      Y                          k              +              1                                )                    ⁢              β        j                  k          +          1                    
with the initial value βik=1, ∀i∈E.
The third step used by the MAP algorithm consists of merging the results of the two recursions to calculate the “a posteriori” probability of the states, by calculating the likelihood ratio of the detected symbols.
The likelihood ratio of a set of states defined by equation (3) can then be expressed as a function of the forward and backward intermediate variables in the following form:
                              Λ          k          X                =                                            ∑                              i                ∈                X                                      ⁢                                          α                i                k                            ⁢                              β                i                k                                                                        ∑                              i                ∉                X                                      ⁢                                          α                i                k                            ⁢                              β                i                k                                                                        (        8        )            
For example, in the context of symbol detection, the set X groups states corresponding to sending the same modulation symbol. In the context of channel decoding, the set X groups states corresponding to the same word at the input to the channel coder.
Although the MAP algorithm supplies very high performance results, it has the disadvantage that it is complex to implement.
In particular, the hardware implementation of the MAP algorithm is very difficult, and consequently receivers implementing this algorithm are expensive.
Problems with implementation of the classical MAP algorithm are partly due to the strong dispersion of probabilities bik that therefore requires high precision for the calculation of the “forward” variable αik and the “backward” variable βik. Moreover, calculation of the likelihood ratio as defined by equation (3) above means that divisions have to be imposed that are expensive and that can cause stability problems.
Log-MAP and Max-Log-MAP type algorithms have been proposed to solve these various disadvantages with the MAP algorithm.
Nevertheless, Log-MAP and Max-Log-MAP type algorithms, like MAP type algorithms, remain very complex to implement and require a large number of operations during the calculation of the likelihood ratio.